package arithmetic.LeetCode;

import java.util.Map;

/**
 * 76. 最小覆盖子串
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * 注意：
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 * <p>
 * 示例 1：
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
 * <p>
 * 示例 2：
 * 输入：s = "a", t = "a"
 * 输出："a"
 * 解释：整个字符串 s 是最小覆盖子串。
 * <p>
 * 示例 3:
 * 输入: s = "a", t = "aa"
 * 输出: ""
 * 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
 * 因此没有符合条件的子字符串，返回空字符串。
 * <p>
 * 链接：https://leetcode.cn/problems/minimum-window-substring
 *
 * @author jiangfeng on 2023/4/25
 */
public class MinWindow {
    public static void main(String[] args) {
        //System.out.println(new Solution().minWindow("ADOBECODEBANC","ABC"));
        //System.out.println(new Solution().minWindow("abc","c"));
        //System.out.println(new Solution().minWindow("ab", "A"));
        System.out.println(new Solution().minWindow("cabwefgewcwaefgcf","cae"));
    }

    static
    class Solution {
        public String minWindow(String s, String t) {
            int slen = s.length(), tlen = t.length();
            if (tlen > slen) {
                return "";
            }
            // 滑动窗口,加hash数组.
            int[] map = new int[58];
            int resLen = tlen;
            int minLen = slen;
            int minL =0;

            //1.先录入t的
            for (int i = 0; i < tlen; i++) {
                map[t.charAt(i) - 'A']--;
            }
            for (int i = 0; i < tlen; i++) {
                if (map[s.charAt(i) - 'A'] < 0) {
                    resLen--;
                }
                map[s.charAt(i) - 'A']++;
            }

            // 2.在录入s的
            int left = 0;
            for (int i = tlen; i < slen; i++) {
                int sIndex = s.charAt(i) - 'A';
                if (map[sIndex] < 0) {
                    resLen--;
                    // 符合条件了
                    if (resLen <= 0 && minLen > i - left + 1) {
                        minLen = i - left + 1;
                        minL=left;
                    }
                }
                map[sIndex]++;

                // 出.尽量卡主在数字里面的
                int leftIndex = s.charAt(left) - 'A';
                while (map[leftIndex] > 0) {
                    // 出的时候也计算一下是否符合条件.
                    if (resLen <= 0 && minLen > i - left) {
                        minLen = i - left;
                        minL=left+1;
                    }
                    map[leftIndex]--;
                    if (left + 1 < slen) {
                        leftIndex = s.charAt(++left) - 'A';
                    }
                }
            }
            if (resLen > 0) {
                return "";
            }
            return s.substring(minL, minL + minLen);

        }
    }

    static class Solution2 {
        public String minWindow(String s, String t) {
            if (t.length() > s.length()) {
                return "";
            }
            // 使用数组来映射 字符.
            // 双指针
            int resLen = 0;
            int[] cmap = new int[64];
            for (int i = 0; i < t.length(); i++) {
                int index = t.charAt(i) - 'A';
                cmap[index]--;
                resLen--;
            }

            for (int i = 0; i < t.length(); i++) {
                int index = s.charAt(i) - 'A';
                if (cmap[index] < 0) {
                    resLen++;
                }
                cmap[index]++;
            }

            if (resLen == 0) {
                return s.substring(0, t.length());
            }
            int l = 0, r = t.length();
            int minLen = s.length();
            int minL = 0;
            while (l <= r && r < s.length()) {
                int indexR = s.charAt(r) - 'A';
                // 右边进一个
                if (cmap[indexR] < 0) {
                    resLen++;
                    // 目前符合要求的最优解,先记录一下
                    if (resLen >= 0 && minLen > r - l + 1) {
                        minLen = r - l + 1;
                        minL = l;
                    }
                }
                cmap[indexR]++;

                int indexL = s.charAt(l) - 'A';
                // 左边出,卡主一个需要的字母. 出到没有需要的字母位置
                // 或者有一种情况,右边进的和左边出的是一样的,且这个字母不再被需要了也可以出.
                while (cmap[indexL] > 0 && l <= r) {
                    cmap[indexL]--;
                    l++;
                    // 再计算一下
                    if (resLen >= 0 && minLen > r - l + 1) {
                        minLen = r - l + 1;
                        minL = l + 1;
                    }
                    if (l < s.length()) {
                        indexL = s.charAt(l) - 'A';
                    }

                }
                r++;
            }
            if (resLen < 0) {
                return "";
            }
            return s.substring(minL, minL + minLen);
        }


        // 1是否包含2
        public boolean contain(Map<Character, Integer> map2, Map<Character, Integer> map1) {
            if (map2.size() < map1.size()) {
                return false;
            }
            for (Character c : map1.keySet()) {
                if (!map1.get(c).equals(map2.get(c))) {
                    return false;
                }
            }
            return true;
        }
    }
}
